For many problems, randomized algorithms are either the fastest algorithm or the simplest algorithm; sometimes they even provide the only known algorithm. Randomized algorithms have become so prevalent that deterministic algorithms could be viewed as a curious special case. In this talk I will describe some startling examples of randomized algorithms for solving some optimization problems on graphs.

Get the Flash Player to see this video using Flash Player.

BitTorrent: Talk (XviD) | Talk (Ogg/Theora) | Talk (MP4) | Talk (MPG)

HTTP (web browser): Talk (XviD) | Talk (Ogg/Theora) | Talk (MP4) | Talk (MPG)